//题目:
// 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？
// 返回满足题意的二叉搜索树的种数。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int numTrees(int n) 
    {
        //1.创建dp表————dp[i]表示：有i个结点时，二叉搜索树的种数
        vector<int> dp(n+1);
        //2.初始化
        dp[0]=1;
        //3.填表————动态转移方程: 
        for(int i=1;i<=n;i++)//固定结点个数
            for(int j=1;j<=i;j++) //挑选根节点
                dp[i]+=dp[j-1]*dp[i-j];
        return dp[n];
    }
};